#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int maxn = 1e4+7;
const int INF = 2147483647;
int n, m, s;
vector<pi> edge[maxn]; // w, v
priority_queue<pi, vector<pi>, greater<pi> > q;
int dis[maxn];
bool vis[maxn];
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin>>n>>m>>s;
  for(int i=0; i<m; ++i) {
    int u, v, w; cin>>u>>v>>w;
    edge[u].push_back({w, v});
  }
  fill(dis+1, dis+1+n, INF);
  dis[s] = 0;
  q.push({0, s});
  while(q.size()) {
    int u = q.top().second; q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(auto [w, v] : edge[u]) {
      if(dis[v] > dis[u] + w) {
        dis[v] = dis[u]+w;
        q.push({dis[v], v});
      }
    }
  }
  for(int i=1; i<=n; ++i) cout<<dis[i]<<' ';
  return 0;
}
